<Day6- 字典, 雜湊表>
集合,字典,雜湊表 存放不重複的值

集合 感興趣的是每個值本身 [值, 值]
字典 我們用 [鍵, 值] 形式來存放資料
雜湊表一樣 以 [鍵, 值] 形式來存放資料

字典 = 映射

• 鍵名用來查詢特定元素
• Es6 有 Map 類別
• 功能：set, remove, has, get ,clear, size, keys,values

雜湊 = 雜湊映射

• 非循序資料結構, 盡可能快速在資料結構中找到一個值
• 雜湊函數作用是給定一個鍵值,然後返回值在表中的位置
• 常見雜湊函數-
  • lose lose : 將每個鍵值中的每個字母的ASCII值相加
  • 可使用javascript String類別中的charCodeAt
• 雜湊表Hashtable 中
  • 欄位 鍵 |雜湊值 | 雜湊表
  • // string |number | table
• 雜湊集合
  • 由一個集合組成, 但是插入,移除,獲取元素時,使用的是雜湊函數
  • 與不同在於,不再添加[鍵-值]對,而只插入[值]沒有鍵(因為是集合)
  • 一樣只存放不重複的值

重點!!! 衝突處理 (當雜湊值相同時如何處理)

1. 分離鏈結
   1. 為雜湊表每一個位置建立一個鏈結串列並將元素存放在裡面
   2. 簡單; 但要在HashTable之外需要額外儲存空間
   3. 方法修改
      1. put
      2. get
      3. remove
2. 線性探查
   1. 如果index被佔住了, 就index+1; index+1若也被佔住了,就index+2 以此類推
   2. 方法修改
      1. put
      2. get
      3. remove
3. 雙雜湊法 略
4. 使用更好的雜湊函數 (降低產生衝突的可能)
   1. 什麼是好的雜湊函數
      1. 插入韓檢所元素的時間(效能)
      2. 較低的衝突可能性
   2. example
      1. djb2
         1. 原理 用大質數(5381) + ASCII *某數(33) 的值 與 大於湊表數量的質數(1013 > 1000) 取餘數
         2. 其他

//字典 like ES6 Map
function Dictionary(){
  let items = {}

  this.set =function(key,value){
    items[key] = value
  }
  this.remove = function(key){
    if(this.has(key)){
      delete items[key]
      return true
    }else {
      return false
    }
  }
  this.has = function(key){
    // 先做這個 會被set, remove呼叫
    return key in items
  }
  this.get = function(key){
    return this.has(key) ? items[key] : undefined
  }
  this.clear = function(){
    items = {}
  }
  this.size = () => Object.keys(items).length
  this.keys = () => Object.keys(items)
  this.values = function(){
    let values = {}
    for (let value in items){
      if(this.has(value)){
        values.push(items[value])
      }
    }
    return values
  }
  this.getItems = () => items
}

//雜湊表 HashTable , HashMap

function HasTable(){
  let table = []

  this.put = function(key, value){
    let position = Hashfunction(key)
    console.log(position + '-' + key );
    table[position] = value
  }
  this.remove = function(key){
    table[Hashfunction(key)] = undefined
  }
  this.get = (key) => table[Hashfunction(key)]
  //先做雜湊函數
  let Hashfunction = function(key){
    let hash = 0 
    for (let i = 0 ; i< key.length ; i++){
      hash += key.charCodeAt(i)
    }
    return hash % 37
  }
  this.print = function(){
    for (var i = 0; i < table.length; ++i) {
      if( table[i] !== undefined){
        console.log(`${i}:${table[i]}`)
      }
    }
  }
}


//解決衝突 1.分離鍵結 待更新
//解決衝突 2.線性探查 待更新

補充資料：

1. SHA-2
2. MD5